#include <vector>

template<typename T>
void selectionSort(T arr[], int n)
{

    for(int i = 0 ; i < n ; i ++){

        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

//冒泡排序
template<typename T>
void BubbleSort(T arr[], int n)
{
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++) {
            if(arr[j] < arr[i]) {
                std::swap(arr[j], arr[i]);
            }
        }
    }
}

// 插入排序
template<typename T>
void insertionSort(T arr[], int n)
{
    int nFlag;
           // 写法1
//        for( int j = i ; j > 0 ; j-- )
//            if( arr[j] < arr[j-1] )
//                swap( arr[j] , arr[j-1] );
//            else
//                break;


    for(int i = 1; i < n; i++) {
        for(int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
            swap(arr[j], arr[j-1]);
        }
    }
}

// 插入排序改进
template<typename T>
void insertionSort1(T arr[], int n)
{
    for(int i = 1; i < n; i++) {
        T e = arr[i];
        int j;
        for(j = i; j > 0 && arr[j - 1] > e; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
}

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename T>
void __merge(T arr[], int l, int mid, int r)
{
    const int len = r - l + 1;
    std::vector<T> aux(len);; // 使用数组的引用来动态分配内存
    
    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }

    int i = 0, j = mid - l + 1;
    for (int k = l; k <= r; k++) {
        if (i > mid - l) {
            arr[k] = aux[j];
            j++;
        } else if (j > len - 1) {
            arr[k] = aux[i];
            i++;
        } else if (aux[i] < aux[j]) {
            arr[k] = aux[i];
            i++;
        } else {
            arr[k] = aux[j];
            j++;
        }
    }
}


// 递归使用归并，对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r)
{
    if(l >= r) {
        return ;
    }

    int mid = (l+r)/2;
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid + 1, r);
    if(arr[mid] > arr[mid+1]) { // 这个速度加快了
        __merge(arr, l, mid, r);
    }
    
}

//归并排序
template<typename T>
void MergeSort(T arr[], int n)
{
    __mergeSort(arr, 0, n-1);
}
